// Package day_11_slider_window_monotone_stack demo-01
// @Title day_11_slider_window_monotone_stack
// @Description
// @Author  == 琳琳也叫王木木 ==  2021/9/4 18:49
// @Create  2021/9/4 18:49
package day_11_slider_window_monotone_stack

import "math"

// 二叉树节点之间的最大问题
/**
二叉树的节点a出发，可以向上走或者向下走，但沿途的节点只能经过一次，到达节点B时
路径上的节点的个数叫做a到b的距离，那么二叉树任意两个节点之间都有距离，
求整棵树上的最大距离

在树形DP的题目中，常见的分类，你要求的那个指标，是包含头结点的还是不包含头节点的？
也就是我要获取的那个标准，是头结点参与的，还是不参与的？
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

type Info struct {
	MaxDis int // 最大距离
	Depth  int // 深度
}

// FindTreeMaxDis 求二叉树的最大距离
func FindTreeMaxDis(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return process(root).MaxDis
}

func process(root *TreeNode) Info {
	if root == nil {
		return Info{0, 0}
	}
	leftInfo := process(root.Left)
	rightInfo := process(root.Right)
	p1 := leftInfo.MaxDis
	p2 := rightInfo.MaxDis
	p3 := leftInfo.Depth + 1 + rightInfo.Depth
	maxDistince := int(math.Max(float64(p3), math.Max(float64(p1), float64(p2))))
	height := int(math.Max(float64(leftInfo.Depth), float64(rightInfo.Depth))) + 1
	return Info{maxDistince, height}
}
